package org.cainiao.algorithm.temp;

import java.util.*;

/**
 * <br />
 * <p>
 * Author: Cai Niao(wdhlzd@163.com)<br />
 */
public class TempTest2 {

    public static void main(String[] args) {
        LRUCache lruCache = new LRUCache(2);
        lruCache.put(1, 1);
        lruCache.put(2, 2);
        System.out.println(lruCache.get(1));
        lruCache.put(3, 3);
        System.out.println(lruCache.get(2));
        lruCache.put(4, 4);
        System.out.println(lruCache.get(1));
        System.out.println(lruCache.get(3));
        System.out.println(lruCache.get(4));

        System.out.println("===");

        int[] case1 = new int[]{1, 2, 3, 1};
        int[] case2 = new int[]{2, 7, 9, 3, 1};
        int[] case3 = new int[]{50, 100, 150, 250, 300, 1050};

        System.out.println(test2(case1));
        System.out.println(test2(case2));
        System.out.println(test2(case3));

        System.out.println(moneyDP(case1));
        System.out.println(moneyDP(case2));
        System.out.println(moneyDP(case3));

        System.out.println(moneyDP2(case1));
        System.out.println(moneyDP2(case2));
        System.out.println(moneyDP2(case3));

        System.out.println("===");

        System.out.println(test3(new Integer[]{1, 3, 2, 5, 3, null, 9}));
        System.out.println(test3(new Integer[]{1, 3, 2, 5, null, null, 9, 6, null, 7}));
        System.out.println(test3(new Integer[]{1, 3, 2, 5}));
    }

    private static int test3(Integer[] tree) {
        int treeLength = tree.length;
        if (treeLength < 1 || tree[0] == null) {
            return 0;
        }
        Queue<Integer> serializedQueue = new LinkedList<>(Arrays.asList(tree));
        Queue<Node> queue = new LinkedList<>();
        Node root = new Node(serializedQueue.poll());
        queue.add(root);

        int maxWidth = 0;
        int widthOfCurrentLevel = 0;
        Node endOfCurrentLevel = root;
        Node endOfNextLevel = null;
        Node startOfCurrentLevel = root;
        Node startOfNextLevel = null;

        while (!queue.isEmpty()) {
            Node node = queue.poll();
            if (node == null) {
                widthOfCurrentLevel++;
                queue.add(null);
                queue.add(null);
                continue;
            }
            Integer left = serializedQueue.poll();
            Integer right = serializedQueue.poll();

            if (left != null) {
                Node leftNode = new Node(left);
                queue.add(leftNode);
                endOfNextLevel = leftNode;
                if (startOfNextLevel == null) {
                    startOfNextLevel = leftNode;
                }
            } else if (node != startOfCurrentLevel && (node != endOfCurrentLevel || right != null)) {
                queue.add(null);
            }

            if (right != null) {
                Node rightNode = new Node(right);
                queue.add(rightNode);
                endOfNextLevel = rightNode;
                if (startOfNextLevel == null) {
                    startOfNextLevel = rightNode;
                }
            } else if (node != endOfCurrentLevel && (node != startOfCurrentLevel || left != null)) {
                queue.add(null);
            }

            widthOfCurrentLevel++;
            if (node == endOfCurrentLevel) {
                if (widthOfCurrentLevel > maxWidth) {
                    maxWidth = widthOfCurrentLevel;
                }
                widthOfCurrentLevel = 0;
                if (endOfCurrentLevel == endOfNextLevel) {
                    break;
                }
                endOfCurrentLevel = endOfNextLevel;
                startOfCurrentLevel = startOfNextLevel;
                startOfNextLevel = null;
            }
        }
        return maxWidth;
    }

    static class Node {
        Integer value;

        public Node(Integer value) {
            this.value = value;
        }
    }

    private static int test2(int[] houses) {
        return money(houses, 0, 0);
    }

    private static int money(int[] houses, int index, int money) {
        return index >= houses.length ? money
            : Math.max(money(houses, index + 1, money), money(houses, index + 2, money + houses[index]));
    }

    private static int moneyDP(int[] houses) {
        int houseCount = houses.length;
        if (houseCount < 1) {
            return 0;
        }
        if (houseCount == 1) {
            return houses[0];
        }
        int total = 0;
        for (int house : houses) {
            total += house;
        }
        return getFromDP(new Integer[houseCount][total], 0, 0, total, houses, houseCount);
    }

    private static int getFromDP(Integer[][] dp, int index, int money, int total, int[] houses, int houseCount) {
        if (index >= houseCount) {
            return money;
        }
        Integer dpValue;
        if (money < total && (dpValue = dp[index][money]) != null) {
            return dpValue;
        }
        if (money >= total) {
            return 0;
        }

        int index1 = index + 1;
        int dpValue1 = getFromDP(dp, index1, money, total, houses, houseCount);

        int index2 = index + 2;
        int money2 = money + houses[index];
        int dpValue2 = getFromDP(dp, index2, money2, total, houses, houseCount);

        int currentDpValue = Math.max(dpValue1, dpValue2);
        dp[index][money] = currentDpValue;
        return currentDpValue;
    }

    private static int moneyDP2(int[] houses) {
        int houseCount = houses.length;
        if (houseCount < 1) {
            return 0;
        }
        if (houseCount == 1) {
            return houses[0];
        }
        int total = 0;
        int max = 0;
        for (int house : houses) {
            total += house;
            if (house > max) {
                max = house;
            }
        }
        return getFromDP2(new MoneyNode[houseCount + 2][total + max], houses, houseCount);
    }

    /**
     * getFromDP2 与 getFromDP 时间复杂度相同，常数项时间也差不多
     * <p>
     * 如果将递归调用看作一棵多叉树，getFromDP 是深度优先遍历，getFromDP2 是从叶子节点向上的宽度优先遍历的话
     * 那么它们的性能没有差别，因为两种情况种，树中的节点都会且仅会被遍历一次
     * 但是，递归调用并不是一棵多叉树，而是一个图，自上而下分出的子节点是可能重叠的
     * 例如 level1_1 节点分出 level2_A、level2_B，level1_2 节点可能分出 level2_A、level2_C，它们在 level2_A 上有重复的子节点
     * 但这并不影响 getFromDP 的时间复杂度，因为第一时间进行了缓存，只要有重复，则一定能缓存命中
     * <p>
     * getFromDP2 每个节点会被稳定访问 2 次
     * 而对于 getFromDP 来说，如果将进入方法与调用递归后返回方法也看作访问 2 次节点的话，那也差不多是一个节点访问两次
     * 当缓存命中时，可以避免已经访问过的子树节点被再次访问
     */
    private static int getFromDP2(MoneyNode[][] dp, int[] houses, int houseCount) {
        MoneyNode root = new MoneyNode(0, 0);
        Stack<MoneyNode> stack = new Stack<>();
        Stack<MoneyNode> stack2 = new Stack<>();
        stack.push(root);
        dp[0][0] = root;
        while (!stack.isEmpty()) {
            MoneyNode node = stack.pop();
            int currentIndex = node.index;
            int currentMoney = node.money;
            int nextIndex = currentIndex + 1;
            int next2Index = currentIndex + 2;
            if (nextIndex == houseCount) {
                dp[currentIndex][currentMoney].dpValue = Math.max(currentMoney, currentMoney + houses[currentIndex]);
            } else {
                stack2.push(node);
                int nextMoney = currentMoney + houses[currentIndex];
                MoneyNode left = new MoneyNode(nextIndex, currentMoney);
                stack.push(left);
                MoneyNode right = new MoneyNode(next2Index, nextMoney);
                if (next2Index == houseCount) {
                    right.dpValue = currentMoney + houses[currentIndex];
                } else {
                    stack.push(right);
                }
                dp[nextIndex][currentMoney] = left;
                dp[next2Index][nextMoney] = right;
            }
        }
        while (!stack2.isEmpty()) {
            MoneyNode node = stack2.pop();
            int currentMoney = node.money;
            int currentIndex = node.index;
            int nextIndex = currentIndex + 1;
            int next2Index = currentIndex + 2;
            int nextMoney = currentMoney + houses[currentIndex];
            if (currentIndex == 0 && currentMoney == 0) {
                return Math.max(dp[nextIndex][currentMoney].dpValue, dp[next2Index][nextMoney].dpValue);
            }
            node.dpValue = Math.max(dp[nextIndex][currentMoney].dpValue, dp[next2Index][nextMoney].dpValue);
        }
        return 0;
    }

    static class MoneyNode {
        int index;
        int money;
        Integer dpValue;

        public MoneyNode(int index, int money) {
            this.index = index;
            this.money = money;
        }

        public MoneyNode(int index, int money, int dpValue) {
            this.index = index;
            this.money = money;
            this.dpValue = dpValue;
        }
    }

    static class LRUCache {
        private final int capacity;
        private final Map<Integer, Node> container = new HashMap<>();
        private final Node oldOpt;
        private final Node newOpt;

        public LRUCache(int capacity) {
            this.capacity = capacity;
            oldOpt = new Node(-1, -1, null, null);
            newOpt = new Node(-1, -1, oldOpt, null);
            oldOpt.next = newOpt;
        }

        public int get(int key) {
            Node node = container.get(key);
            if (node == null) {
                return -1;
            }
            if (node.next != newOpt) {
                moveToNew(node);
            }
            return node.value;
        }

        public void put(int key, int value) {
            Node node = container.get(key);
            if (node == null) {
                if (container.size() == capacity) {
                    container.remove(oldOpt.next.key);
                    removeFromLinkedList(oldOpt.next);
                }
                node = new Node(key, value, newOpt.pre, newOpt);
                putInToNew(node);
                container.put(key, node);
            } else {
                node.value = value;
                moveToNew(node);
            }
        }

        private void moveToNew(Node node) {
            removeFromLinkedList(node);
            node.pre = newOpt.pre;
            node.next = newOpt;
            putInToNew(node);
        }

        private void putInToNew(Node node) {
            newOpt.pre.next = node;
            newOpt.pre = node;
        }

        private void removeFromLinkedList(Node node) {
            node.pre.next = node.next;
            node.next.pre = node.pre;
        }

        static class Node {
            int key;
            int value;
            Node pre;
            Node next;

            public Node(int key, int value, Node pre, Node next) {
                this.key = key;
                this.value = value;
                this.pre = pre;
                this.next = next;
            }
        }
    }
}
